#include <iostream>
#include <string>
#include <queue>
#include <stack>
using namespace std;


struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

//class Solution {
//public:
//    void string_add(TreeNode* root, string& st)
//    {
//        if (root == nullptr)
//        {
//            return;
//        }
//        st += to_string(root->val);
//        if (root->left || root->right)
//        {
//            st += '(';
//            string_add(root->left, st);
//            st += ')';
//        }
//        if (root->right)
//        {
//            st += '(';
//            string_add(root->right, st);
//            st += ')';
//        }
//    }
//
//    string tree2str(TreeNode* root) {
//        string st;
//        string_add(root, st);
//        return st;
//    }
//};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if (root == nullptr)
        {
            return ret;
        }
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty())
        {
            int n = q.size();
            vector<int> v;
            while (n--)
            {
                TreeNode* node = q.front();
                q.pop();
                TreeNode* left = node->left;
                TreeNode* right = node->right;
                if (left)
                {
                    q.push(node->left);
                }
                if (right)
                {
                    q.push(node->right);
                }
                v.push_back(node->val);
            }
            ret.push_back(v);
        }
        return ret;
    }
};

//int main()
//{
//    TreeNode* node = new TreeNode(1);
//    node->left = new TreeNode(2);
//    node->right = new TreeNode(3);
//    node->right->left = new TreeNode(4);
//    node->right->right = new TreeNode(5);
//    Solution s;
//    vector<vector<int>> ret = s.levelOrder(node);
//    for (auto s1 : ret)
//    {
//        for (auto s2 : s1)
//        {
//            cout << s2 << " " << endl;
//        }
//    }
//    return 0;
//}

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ret;
        if (root == nullptr)
        {
            return ret;
        }
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty())
        {
            int n = q.size();
            vector<int> v;
            while (n--)
            {
                TreeNode* node = q.front();
                q.pop();
                TreeNode* left = node->left;
                TreeNode* right = node->right;
                if (left)
                {
                    q.push(node->left);
                }
                if (right)
                {
                    q.push(node->right);
                }
                v.push_back(node->val);
            }
            ret.push_back(v);
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr)
        {
            return nullptr;
        }
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (root == p)
        {
            return p;
        }
        if (root == q)
        {
            return q;
        }
        if (left && right)
        {
            return root;
        }
        if (left)
        {
            return left;
        }
        if (right)
        {
            return right;
        }
        return nullptr;
    }
};

class Solution {
public:
    TreeNode* phead = nullptr;
    TreeNode* prev = nullptr;
    void list_tree(TreeNode* root)
    {
        if (root == nullptr)
        {
            return;
        }
        list_tree(root->left);
        if (prev)
        {
            prev->right = root;
        }
        else
        {
            phead = root;
        }
        root->left = prev;
        prev = root;
        list_tree(root->right);
    }
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if (pRootOfTree == nullptr)
        {
            return nullptr;
        }
        list_tree(pRootOfTree);
        return phead;
    }
};
